package 算法.十大排序算法;

import java.util.Arrays;

/**
 * @author coderFu
 * @create 2022/3/18
 * 基数排序
 * 整个思想，先把数据以个位进行分配桶位，将数据放到桶里面
 * 然后依次从桶中取出数据
 */
public class CoderRadixSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2,3,3,43,25,4333,6,45,6,49};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] array){
        // d 表示该数组中的最高位 ， 可以通过一次遍历确定
        int d = 0;
        for(int i=0; i< array.length; i++){
            String s = array[i]+"";
            if(s.length() > d){
                d = s.length();
            }
        }
        d = (int)Math.pow(10,d-1);
        System.out.println(d);
        // 分离原则1， 10 ，100
        int division = 1;
        // 存储每个桶中的数据
        int[] count = new int[10];
        // 存储每次排序后的值
        int[][] bucket = new int[10][array.length];

        while (division <= d){
            // 存储数据到桶中
            for(int i=0; i<array.length; i++){
                // 获取其个位，找到在桶中的位置
                int digit = (array[i]/division)%10;
                bucket[digit][count[digit]]= array[i];
                count[digit]++;
            }
            int k = 0;

            // 取数据
            for(int i=0; i< 10; i++){
                for(int j=0; j<count[i]; j++){
                    array[k] = bucket[i][j];
                    k++;
                }
                count[i] = 0;
            }
            division = division*10;
        }

    }
}
